package pro.softzhang.algo.lc1400;

import pro.softzhang.algo.flag.knowledge.KGraph;

import java.util.ArrayList;
import java.util.List;

/**
 * 1466. 重新规划路线
 * https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero
 */
@KGraph
public class LC1466_ReorderRoutesToMakeAllPathsLeadToTheCityZero {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int minReorder(int n, int[][] connections) {
            List<int[]>[] e = new List[n];
            for (int i = 0; i < n; i++) {
                e[i] = new ArrayList<int[]>();
            }
            for (int[] edge : connections) {
                e[edge[0]].add(new int[]{edge[1], 1});
                e[edge[1]].add(new int[]{edge[0], 0});
            }
           return dfs(0, -1, e);
        }

        private int dfs(int x, int parent, List<int[]>[] e) {
            int res = 0;
            for (int[] edge : e[x]) {
                if (edge[0] == parent) {
                    continue;
                }
                res += edge[1] + dfs(edge[0], x, e);
            }
            return res;
        }
    }
}
